<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>
<body>
    <script>
        var arrs = [7,5,3,6,1,4,2,9,8];

        //    找一个基准值 
        //    准备两个空数组   遍历数组  比基准值小 放左边  大 放右边


        // 左边的数组  也 找基准值   准备空数组   右边的数组 也执行这样的操作  
        // 左边处理的结果 + 基准值  + 右边处理的结果  看看是不是到达结束条件 
        // 没有达到结束条件  返回 
        // 1.写函数
        // 2.结束条件
        // 3. 没有达到结束条件 返回
        function quicksort(arr){
            //结束条件 
            if(arr.length<=1){
                return arr;
            }



            //如果没有达到结束条件 那么找基准值  
            // 准备两个空数组  小 左 大 右 
            // 左边的  和右边的数组 继续做这样的事情

            var target = arr[arr.length-1];
            var left=[],right=[];
            for(var key of arr){
                if(key < target){
                    left.push(key)
                }
                else if(key > target){
                    right.push(key)
                }
            }

            return quicksort(left).concat(target,quicksort(right)); 


        }
        
        console.log(quicksort(arrs));

        // 如果 数组中有重复的元素 那么不能用快排 
        // 快排的结果只留下其中一个  
    </script>
</body>
</html>